#include "string_array.h"
#include<iostream>
#include<vector>

using namespace std;

//myStr构造函数
myStr::myStr(const char* str){
    int i = 0;
    if(str){
    while(str[i] != '\0') i++; // 循环直到找到字符串结束符
    length = i;
    data = new char[length+1];//"\0"
    for(i=0;i<length;i++)
        data[i] = str[i];
        data[length] = '\0';
    }
    next = new int[length+1];
    for(i=0;i<length+1;i++) next[i] = 0;
    nextVal = new int[length+1];
    for(i=0;i<length+1;i++) nextVal[i] = 0;
}

//myStr析构函数
myStr::~myStr(){
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

//StrLength
/*int myStr::StrLength(const char* str) {
    int i = 0;
    while (str[i] != '\0') i++; // 循环直到找到字符串结束符
    return i; // 返回字符串长度
}

//StrCopy
void myStr::StrCopy(const char* str) {
    for (int i = 0; str[i] != '\0'; i++) {
        data[i] = str[i]; // 复制字符串直到'\0'
    }
    data[length] = '\0'; // 确保复制的字符串以'\0'结尾
}
*/

//bool replaceStr串的替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int tLen = T.length; // 子串T的长度
    int vLen = V.length; // 子串V的长度
    int sLen = S.length; // 字符串S的长度

    // 检查起始位置是否有效
    if (start < 1 || start > sLen - tLen + 1) return 0;

    // 从start位置开始查找子串T
    for (int i = start - 1; i <= sLen - tLen; i++) {
        bool match = true; // 假设匹配
        for (int j = 0; j < tLen; j++) {
            if (S.data[i + j] != T.data[j]) {
                match = false; // 不匹配
                break;
            }
        }
        // 如果找到匹配的子串T 
        if (match) {
            // 处理替换逻辑
            if (vLen > tLen) { // 如果V比T长，需要移动后面的字符
                for (int k = sLen; k >= i + tLen; k--) {
                    S.data[k + vLen - tLen] = S.data[k];
                }
                // 更新S的长度
                sLen += vLen - tLen;
            } 
            else if (vLen < tLen) { // 如果V比T短，需要删除多余的字符
                for (int k = i + tLen; k < sLen; k++) {
                    S.data[k + vLen - tLen] = S.data[k];
                }
                // 更新S的长度
                sLen -= tLen - vLen;
            }
            // 复制V到S中
            for (int k = 0; k < vLen; k++) {
                S.data[i + k] = V.data[k];
            }
            // 更新S的长度
            S.length = sLen;
            return 1; // 返回成功
        }
    }
    return 0; // 没有找到匹配的子串T
}

//simpleMatch
int simpleMatch(const myStr& S, const myStr& T){
    if(S.length < T.length|| T.length == 0) return -1;

    int pos =0;//返回的位置
    int sLen = S.length;//目标串S的长度
    int tLen = T.length;//模式串T的长度
    for(int i = 0; i <= sLen - tLen; i++){
        bool match = true;//假设匹配
        for(int j = 0; j < tLen; j++){
            if(S.data[i+j] != T.data[j]){   
                match = false; // 不匹配
                break;
            }
        }
        pos++;//位置+1
        if(match)
            return pos;//成功匹配 返回位置
    }
    return -1;//不匹配
}

//KMP辅助next的计算
void myStr::kmp_next() const{
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<length){
        if(j==-1||data[i]==data[j]){
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
    for(int i = 0; i < length; i++)
        next[i] = next[i] + 1;
}

/*
void myStr::kmp_next() const{
    if(length == 1) next[0] = 0;//定义计算next数组
    else if(length == 2) next[1]=1;
    else{
        next[0] = 0;next[1] = 1;
        next[2] = (data[0] == data[1]) ? 2 : 1;
        for(int i = 3;i<length;i++){//递推
            int j=next[i-1];
            while(j>1&&data[i] != data[j]){//前面有真子串且添加的字符还不能构成真子串
                j = next[j-1];
            }   
            if(data[i] == data[j]){
                next[i] = j+1;//满足当前字符串前缀后缀真字串
            }            
            else next[i] = j;
        }
    }
}
*/


//KMP辅助nextVal的计算
void myStr::kmp_nextVal() const{
    int i=0;
    int j=-1;
    nextVal[0]=-1;
    while(i<length){
        if(j==-1||data[i]==data[j]){
            i++;
            j++;
            if(data[i] != data[j]) nextVal[i]=j;
            else nextVal[i]=nextVal[j];
        }
        else j=nextVal[j];
    }
    for(int i = 0; i < length; i++)
        nextVal[i] = nextVal[i] + 1;
}
/*
void myStr::kmp_nextVal() const{
    if(length == 1) nextVal[0] = 0;//定义计算nextVal数组
    else{
        nextVal[0] = 0;
        int i=1;
        int j=0;//j=i-1
        while (i < length) {
        if (j == 0 || data[i] == data[j]) {
            if (data[i] == data[j]) j++;//j为当前字串真子串长度
            i++;
            if (j > 0 && data[i] != data[j]) nextVal[i] = nextVal[j];
            else nextVal[i] = j;//next[i]
        } 
        else j = nextVal[j];
    }
    }
}
*/
//kmpMatch
int kmpMatch(const myStr& S, const myStr& T){
    int sLen = S.length;//目标串S的长度
    int tLen = T.length;//模式串T的长度
    int pos = 0;//返回的位置


    int j = 0; // i是目标串S的索引，j是模式串T的索引
    if(tLen == 0||tLen > sLen) return -1; // 空串或模式串长度大于目标串长度，返回-1
    while (pos < sLen && j < tLen) {
        if (S.data[pos] == T.data[j]) {
            pos++;
            j++;
            if (j == tLen) {
                // 匹配成功，立即返回匹配的起始位置
                return pos - j+1;
            }
        }
        else  {
            if (j!= 0) {
                j = T.nextVal[j-1];//不匹配，j回退到nextVal[j]位置

            }
            else {
                pos++;
            }
        }
    }
    return -1;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//myMatrix构造函数
myMatrix::myMatrix(const int& row, const int& col,const int& num,const int* data){
    rowNum = row;
    colNum = col;
    nodeNum = num;
    if(nodeNum > 0){
    nodeList = new matrixNode[nodeNum];
        for (int i = 0; i < nodeNum; i++) {
            nodeList[i].row = data[i * 3];
            nodeList[i].col = data[i * 3 + 1];
            nodeList[i].value = data[i * 3 + 2];
        }
        // 使用冒泡排序或其他排序算法对 nodeList 进行排序
        for (int i = 0; i < nodeNum - 1; i++) {
            for (int j = 0; j < nodeNum - i - 1; j++) {
                if (nodeList[j].row > nodeList[j + 1].row ||
                    (nodeList[j].row == nodeList[j + 1].row && nodeList[j].col > nodeList[j + 1].col)) {
                    matrixNode temp = nodeList[j];
                    nodeList[j] = nodeList[j + 1];
                    nodeList[j + 1] = temp;
                }
            }
        }
    }
}

//myMatrix析构函数
myMatrix::~myMatrix(){
    delete[] nodeList;
}

//按行优先的稀疏矩阵排列
/*
void myMatrix::RowFirstMatrix(){
    for(int i = 0; i < nodeNum; i++){
        if(nodeList[i].row > nodeList[i+1].row || (nodeList[i].row == nodeList[i+1].row && nodeList[i].col > nodeList[i+1].col)){
            int temp = nodeList[i].row;
            int temp2 = nodeList[i].col;
            int temp3 = nodeList[i].value;
            nodeList[i].row = nodeList[i+1].row;
            nodeList[i].col = nodeList[i+1].col;
            nodeList[i].value = nodeList[i+1].value;
            nodeList[i+1].row = temp;
            nodeList[i+1].col = temp2;
            nodeList[i+1].value = temp3;
        }
    }
}
*/

//快速转置矩阵
void myMatrix::FastTransposeSMatrix(myMatrix& T){
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;

    std::vector<int> num(T.rowNum, 0);
    for (int i = 0; i < nodeNum; ++i) {
        num[nodeList[i].col]++;
    }

    std::vector<int> cpot(T.rowNum);
    cpot[0] = 0;
    for (int i = 1; i < T.rowNum; ++i) {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }

    T.nodeList = new matrixNode[nodeNum];
    for (int i = 0; i < nodeNum; ++i) {
        int destIndex = cpot[nodeList[i].col];
        T.nodeList[destIndex].row = nodeList[i].col;
        T.nodeList[destIndex].col = nodeList[i].row;
        T.nodeList[destIndex].value = nodeList[i].value;
        cpot[nodeList[i].col]++;
    }
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
